Over the years, switching systems having a wide variety of architectures have been developed for use in telecommunication networks. A “crossbar” switch is a single-stage, single-path, non-blocking switch. Broadly speaking, an N by N crossbar switch consists of a square array of N2 individually operated crosspoints, one for each input-output pair, having two possible states—cross (default) and bar. For such an N by N crossbar switch, a connection between input port i and output port j is established by setting the (i, j) crosspoint switch to the bar state.
Crossbar switches have always been attractive to switch designers because they are non-blocking, relatively simple in architecture and modular in nature. Originally developed for circuit switching, many asynchronous transfer mode (“ATM”) switching systems are either based on the crossbar switch or use it as their basic building block. Crossbar switches do, however, have several drawbacks. First and foremost, crossbar switches have a square growth of complexity. As a result, they do not scale well to large sizes. Additionally, different input-output pairs of a crossbar switch may have different transit delays. As a result, a fairness problem arises when the crossbar switch is operated in a self-routing mode. Finally, despite being non-blocking, crossbar switches suffer from output blocking. As a result, buffers are oftentimes necessary to reduce cell losses in ATM switching systems based upon crossbar switch technology.
Other ATM switching systems are based upon a network architecture commonly referred to as a “Banyan” network. Besides being self-routing, Banyan network-based switching systems are modular, generally have the same latency for all input-output pairs, support synchronous and asynchronous modes of operation, are suitable for very large scale implementation (“VLSI”) implementations, and enjoy reduced complexity in comparison to the crossbar switch. However, while the Banyan network's path-uniqueness characteristic preserves cell sequencing in Banyan network-based switching systems, it results in the switching systems being internally blocking. Thus, while the Banyan network-based switching systems and the crossbar switch-based switching systems both suffer from degraded performance when the size of the switching system is increased, the degradation is more significant for the Banyan network-based switching systems because the crossbar switching system suffers only from output blocking while the Banyan network-based switching system suffers from both output blocking and an internal blocking which increases in severity with the number of stages therein.
A Banyan network-based switching system may become non-blocking if incoming cells are ordered according to their output port addresses and concentrated to remove any gaps between active inputs if output conflicts do not exist. A network architecture which, if incorporated into a Banyan network-based switching system, that can perform distributed parallel sorting is generally referred to as a “Batcher” sorter network. An N by N Batcher sorter network can be constructed using log2(log2N+1)/2 stages, each with N/2 sorting elements, for example, binary comparators. A Batcher sorter network can sort an arbitrary set of active cells based upon their output port addresses and group them consecutively at either the bottom or top of its output ports.
An ATM switching system 150 which combine the aforedescribed Batcher sorter and Banyan networks is illustrated in FIG. 1a. The ATM switching system 150, commonly referred to as a “Sunshine” switching system, is comprised of a Batcher sorter network 152, trap network 154, a concentrator 156, a selector 158, a recirculating buffer 160, a parallel array of Banyan networks 162-1 through 162-N and a parallel array of output buffers 164-1 through 164-N. Cells input the ATM switching system 150 first enter the Batcher sorter network 152. The Batcher sorter network 152 arranges the cells in order of destination address and priority. The sorted cells proceed to the trap network 154 for resolution of output port contention. More specifically, the trap network 154 resolves output port contention by selecting the k highest priority cells present for each destination address within a time slot for routing to the parallel array of Banyan networks 162-1 through 162-N. Any excess cells for each destination address are selected for routing to the recirculation buffer 160 from those to be routed to the parallel array of Banyan networks 162-1 through 162-N and the selector 158 selectively directs the separated cells to either the recirculation buffer 160 or the parallel array of Banyan networks 162-1 through 162-N as appropriate.
The parallel array of k Banyan networks 162-1 through 162-N provides k independent paths for cells to access the output buffers 164-1 through 164-N. Thus, as many as k cells may request a single destination address in a single time slot. If more than k cells request the same destination address, the excess cells are instead directed into the recirculating buffer 160. There, the excess cells are held until the next time slot and then resubmitted to the Batcher sorter network 152. Thus, ATM switching system 150 recirculates excess cells requesting the same address and must dedicate a number of input ports for recirculating cells. Accordingly, while the ATM switching system 150 can handle k cells requesting the same destination address, once the number of cells requesting that destination address exceeds k, performance of the ATM switching system 150 begins to suffer. Finally, because the ATM switching system 150 cannot be readily partitioned into integrated circuits, its commercial applicability is relatively limited.
Another ATM switching system 166 which incorporates a Batcher sorter network, here, without an associated parallel array of Banyan networks, is illustrated in FIG. 1b. The ATM switching system 166, commonly referred to as a “Starlite” switching system, includes a concentrator 168, a Batcher sorter network 170, a trap network 172, a recirculation buffer 174 and an expander 176. For the ATM switching system 166, cells arriving at the Batcher sorter network 170 within a time slot are sorted based upon destination address. The outputs of the Batcher sorter network 170 are fed into the trap network 172 in ascending order. The trap network 172 detects plural cells having the same destination address and allows only one of the plural cells destined to the same output port to be admitted to the expander 176. The remaining cells destined to that output port are recycled back to the Batcher sorter network 170 through the recirculation buffer 174. While the ATM switching system 166 suffers from a number of deficiencies, one of the more glaring of such deficiencies is that, in order to reduce cell loss within the recirculation buffer 174 a substantial fraction of the input ports of the Batcher sorter network 170 must be dedicated for cells being recirculated from the trap network 172 via the recirculating buffer 174. In the absence of such a need, these input ports would instead be dedicated to the concentrator 168. Thus, because of the need to dedicate a substantial number of ports to the recirculation buffer 174, the probability of cell loss within the concentrator 168 increases and the overall utilization rate of the ATM switching system 166 decreases substantially.
This invention improves on current switching systems such as the aforementioned Starlite and Sunshine switching systems by providing the advantages of a higher performance switching system without need of relatively complex hardware configurations therefor.